package class03;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.TreeSet;

// 题目描述：
// 在电子游戏"辐射4"中，任务"通向自由"要求玩家到达名为"Freedom Trail Ring"的金属表盘，
// 并使用表盘拼写特定关键词才能开门。
// 给定一个字符串 ring，表示刻在外环上的编码；给定另一个字符串 key，
// 表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。
//
// 最初，ring 的第一个字符与 12:00 方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，
// 然后按下中心按钮，以此逐个拼写完 key 中的所有字符。
//
// 旋转 ring 拼出 key 字符 key[i] 的阶段中：
// - 您可以将 ring 顺时针或逆时针旋转 1 步，计为1步。
// - 如果字符 key[i] 已经在 12:00 方向对齐，也需要按下中心按钮进行拼写，计为1步。
// - 按下中心按钮后，您可以开始拼写 key 中的下一个字符（下一阶段），直至完成所有拼写。
//
// 示例 1:
// 输入: ring = "godding", key = "gd"
// 输出: 4
// 解释:
// 对于 key 的第一个字符 'g'，已经在正确的位置，我们只需要1步来拼写这个字符。
// 对于 key 的第二个字符 'd'，我们需要逆时针旋转 ring "godding" 2步使其变成 "ddinggo"。
// 当然，我们还需要1步进行拼写。因此最终的输出是 4。
//
// 示例 2:
// 输入: ring = "godding", key = "godding"
// 输出: 13
//
// 提示：
// 1 <= ring.length, key.length <= 100
// ring 和 key 只包含小写英文字母
// 保证字符串 key 一定可以由字符串 ring 旋转拼出
//
// 解题思路：
// 这是一个典型的动态规划问题。我们需要找到从一个位置到另一个位置的最短路径，
// 并考虑所有可能的路径选择。
//
// 方法一：记忆化搜索
// 1. 预处理：记录每个字符在ring中出现的所有位置
// 2. 状态定义：dp[i][j]表示当前指针在ring的第i个位置，需要匹配key中从第j个字符开始的子串所需的最少步数
// 3. 状态转移：对于当前位置i和当前需要匹配的字符key[j]，枚举该字符在ring中的所有位置k，
//    计算从位置i到位置k的最短距离，然后递归求解从位置k匹配key[j+1...]的最少步数
//
// 方法二：优化的记忆化搜索
// 1. 利用TreeSet的floor和ceiling方法，快速找到当前位置左边和右边最近的目标字符位置
// 2. 只需要考虑向左和向右两个方向中最近的位置，避免了枚举所有可能位置
// 3. 这种贪心策略是正确的，因为选择更远的位置不会比选择最近位置更优
//
// 本题测试链接 : https://leetcode.com/problems/freedom-trail/
public class Code07_FreedomTrail {

	// 提交时把findRotateSteps1方法名字改成findRotateSteps可以直接通过
	public static int findRotateSteps1(String r, String k) {
		// 将ring字符串转换为字符数组
		char[] ring = r.toCharArray();
		// 获取ring的长度
		int N = ring.length;
		// 创建一个HashMap，用于存储每个字符在ring中出现的位置
		HashMap<Character, ArrayList<Integer>> map = new HashMap<>();
		// 遍历ring数组，记录每个字符出现的位置
		for (int i = 0; i < N; i++) {
			// 如果当前字符还没有在map中记录过，则创建一个新的ArrayList
			if (!map.containsKey(ring[i])) {
				map.put(ring[i], new ArrayList<>());
			}
			// 将当前字符的位置添加到对应的列表中
			map.get(ring[i]).add(i);
		}
		// 将key字符串转换为字符数组
		char[] str = k.toCharArray();
		// 获取key的长度
		int M = str.length;
		// 创建动态规划表，dp[i][j]表示当前指针在位置i，需要匹配key中从索引j开始的字符所需的最少步数
		int[][] dp = new int[N][M + 1];
		// hashmap
		// dp[][] == -1 : 表示没算过！
		// 初始化dp表，将所有位置标记为-1，表示尚未计算
		for (int i = 0; i < N; i++) {
			for (int j = 0; j <= M; j++) {
				dp[i][j] = -1;
			}
		}
		// 调用递归函数开始计算，初始状态为指针在位置0，需要匹配key中从索引0开始的字符
		return process(0, 0, str, map, N, dp);
	}

	// 电话里：指针指着的上一个按键preButton
	// 目标里：此时要搞定哪个字符？keyIndex
	// map : key 一种字符 value: 哪些位置拥有这个字符
	// N: 电话大小
	// f(0, 0, aim, map, N)
	public static int process(int preButton, int index, char[] str, HashMap<Character, ArrayList<Integer>> map, int N,
			int[][] dp) {
		// 如果已经计算过该状态，则直接返回结果
		if (dp[preButton][index] != -1) {
			return dp[preButton][index];
		}
		// 初始化结果为最大值
		int ans = Integer.MAX_VALUE;
		// 如果已经处理完所有key中的字符，则不需要额外步数
		if (index == str.length) {
			ans = 0;
		} else {
			// 还有字符需要搞定呢！
			// 获取当前需要匹配的字符
			char cur = str[index];
			// 获取当前字符在ring中所有出现的位置
			ArrayList<Integer> nextPositions = map.get(cur);
			// 遍历所有可能的位置
			for (int next : nextPositions) {
				// 计算从当前位置preButton到目标位置next所需的步数，加上按下按钮的1步，再加上后续操作的步数
				int cost = dial(preButton, next, N) + 1 + process(next, index + 1, str, map, N, dp);
				// 更新最小步数
				ans = Math.min(ans, cost);
			}
		}
		// 将计算结果存入dp表中
		dp[preButton][index] = ans;
		// 返回结果
		return ans;
	}

	// 计算在环形结构中从位置i1到位置i2的最短距离
	public static int dial(int i1, int i2, int size) {
		// 返回顺时针和逆时针两种路径中的较短者
		return Math.min(Math.abs(i1 - i2), Math.min(i1, i2) + size - Math.max(i1, i2));
	}

	// 以下方法来自陆振星同学
	// 可以省掉枚举行为
	// 提交时把findRotateSteps2方法名字改成findRotateSteps可以直接通过
	// 来龙去脉 : https://www.mashibing.com/question/detail/67299
	// 例 :
	// ring = aaca
	// key = ca
	// 首先来到 2 位置的 c, 下一步有 0 1 3 三个位置的 a 可以选择
	// 只需要在 1 3 里面选择最优的即可, 因为 0 位置的 a 在任何情况下都不会比 1 位置的 a 更优
	// 这是对的
	// 应该是可以的，课上讲述的方法根据数据量能过，就没有继续优化了。
	// 如下的贪心方式不对：
	// 当前来到的位置，然后要去下一个字符，左边离下一个字符近就选左边，左边离下一个字符近就选右边。
	// 两条路只选1条，彻底的每一步都选当前步最优。
	// 但陆振星同学的贪心方式是：
	// 1）当前来到的位置，然后要去下一个字符，左边离下一个字符最近的位置，去往左边，然后可能性展开，选最好的解；
	// 2）当前来到的位置，然后要去下一个字符，右边离下一个字符最近的位置，去往右边，然后可能性展开，选最好的解；
	// 1）和2）中最好的解，选出来，返回。
	// 这是对的，因为如果去往离左右两边都更远的位置，那么为什么不在走的过程中，顺带就满足了下一个字符呢？
	// 这样还能省掉枚举行为
	// 如下所有代码都提交，再次注意：提交时把findRotateSteps2方法名字改成findRotateSteps可以直接通过
	// ring的长度
	private int ringLength;
	// key字符数组
	private char[] key;
	// 存储每个字符在ring中出现位置的TreeSet列表
	private ArrayList<TreeSet<Integer>> ringSet;
	// 记忆化搜索的dp表，存储已计算过的状态
	private final HashMap<Integer, Integer> dp = new HashMap<>();

	public int findRotateSteps2(String ring, String key) {
		// 将ring字符串转换为字符数组
		char[] chars = ring.toCharArray();
		// 将key字符串转换为字符数组
		this.key = key.toCharArray();
		// 获取ring的长度
		ringLength = chars.length;
		// 初始化ringSet，为每个字母创建一个TreeSet
		ringSet = new ArrayList<>();
		for (int i = 0; i < 26; i++) {
			ringSet.add(new TreeSet<>());
		}
		// 遍历chars数组，将每个字符的位置记录到对应的TreeSet中
		for (int i = 0; i < chars.length; i++) {
			ringSet.get(chars[i] - 'a').add(i);
		}
		// 调用递归函数开始计算，初始状态为需要匹配key中从索引0开始的字符，当前指针在位置0
		return findRotateSteps(0, 0);
	}

	// kIndex : 当前要搞定的字符
	// cur : 当前所在的位置
	private int findRotateSteps(int kIndex, int cur) {
		// 如果已经处理完所有key中的字符，则不需要额外步数
		if (kIndex == key.length) {
			return 0;
		}
		// kIndex 和 cur 的最大值为 100, 所以用 十进制的低两位 表示 cur, 用高两位表示 kIndex
		// 构造状态key，用于在dp表中查找是否已经计算过该状态
		int k = kIndex * 100 + cur - 1;
		// 在dp表中查找该状态是否已经计算过
		Integer v = dp.get(k);
		// 如果已经计算过，则直接返回结果
		if (v != null) {
			return v;
		} else {
			// 否则初始化结果为最大值
			v = Integer.MAX_VALUE;
		}
		// key[kIndex] 的所有位置
		TreeSet<Integer> treeSet = ringSet.get(key[kIndex] - 'a');
		// 从 cur 向左走, 最近的符合 key[kIndex] 的位置
		// 获取小于等于当前指针位置的最近位置
		Integer floor = treeSet.floor(cur);
		// 如果没有找到，则取最大的位置（环形结构）
		if (floor == null) {
			floor = treeSet.last();
		}
		// 计算从当前位置到目标位置的距离
		int len = Math.abs(cur - floor);
		// 取顺时针和逆时针中的较短距离
		len = Math.min(len, ringLength - len);
		// 更新最小步数：距离 + 按钮操作1步 + 后续操作的步数
		v = Math.min(v, len + 1 + findRotateSteps(kIndex + 1, floor));
		// 从 cur 向右走, 最近的符合 key[kIndex] 的位置
		// 获取大于等于当前指针位置的最近位置
		Integer ceiling = treeSet.ceiling(cur);
		// 如果没有找到，则取最小的位置（环形结构）
		if (ceiling == null) {
			ceiling = treeSet.first();
		}
		// 计算从当前位置到目标位置的距离
		len = Math.abs(cur - ceiling);
		// 取顺时针和逆时针中的较短距离
		len = Math.min(len, ringLength - len);
		// 更新最小步数：距离 + 按钮操作1步 + 后续操作的步数
		v = Math.min(v, len + 1 + findRotateSteps(kIndex + 1, ceiling));
		// 将计算结果存入dp表中
		dp.put(k, v);
		// 返回结果
		return v;
	}

}
